package InterviewQuestions;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: wangliuyang
 * @Date: 2021/6/17 16:06
 * @Description: LRU
 */
public class LRU {
    public Map<Integer, Node> map;
    public DoubleLinkNode linkNode;
    public int capacity;

    public LRU(int capacity) {
        linkNode = new DoubleLinkNode();
        map = new HashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            linkNode.removeToTail(node);
            return node.v;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.v = value;
            linkNode.removeToTail(node);
        } else {
            Node node = new Node(key, value);
            if (capacity <= map.size()) {
                Node head = linkNode.deleteNode(linkNode.head);
                map.remove(head.k);
            }
            linkNode.addNode(node);
            map.put(key, node);
        }
    }

    class Node {
        public int k;
        public int v;
        public Node pre;
        public Node last;

        public Node(int k, int v) {
            this.k = k;
            this.v = v;
        }
    }

    class DoubleLinkNode {
        public Node head;
        public Node tail;

        public DoubleLinkNode() {
            this.head = null;
            this.tail = null;
        }

        public void removeToTail(Node node) {
            Node node1 = deleteNode(node);
            addNode(node1);
        }

        /*
        尾插法插入节点
         */
        public void addNode(Node node) {
            if (tail == null) {
                head = tail = node;
            } else {
                tail.last = node;
                node.pre = tail;
                tail = tail.last;
            }
        }

        /*
        删除节点
         */
        public Node deleteNode(Node node) {
            if (head == tail) {
                head = tail = null;
                return node;
            }
            if (node == tail) {
                tail = tail.pre;
                tail.last = null;
            } else if (node == head) {
                head = head.last;
                head.pre = null;
            } else {
                node.pre.last = node.last;
                node.last.pre = node.pre;
            }
            return node;
        }
    }
}
